package SubjectBacktracking.Four;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class SolveNQueens {

/**
 * 难度：困难
 * 
 * 51. N 皇后
 * 	n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
 * 	给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
 * 	每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
 * 	
 * 示例 1：
 * 	输入：n = 4
 * 	输出：[[	".Q..",
 * 			"...Q",
 * 			"Q...",
 * 			"..Q."]
 * 		,
 * 		 [	"..Q.",
 * 			"Q...",
 * 			"...Q",
 * 			".Q.."]]
 * 	解释：如上图所示，4 皇后问题存在两个不同的解法。
 * 	
 * 示例 2：
 * 	输入：n = 1
 * 	输出：[["Q"]]
 * 	
 * 提示：
 * 	1 <= n <= 9
 * 	皇后彼此不能相互攻击，也就是说：任何两个皇后都不能处于同一条横行、纵行或斜线上。
 *
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		SolveNQueens snq = new SolveNQueens();
		System.out.println(snq.solveNQueens1(4));
	}

	//自己写
	List<List<String>> result = new ArrayList<>();
	public List<List<String>> solveNQueens(int n) {
		//创建棋盘数组,全部填充"."
		String[][] chessboard = new String[n][n];
		for(int i=0;i<n;i++) {
			Arrays.fill(chessboard[i], ".");
		}
		backtracking(n, 0, chessboard);
		return result;
    }
	public void backtracking(int n, int row, String[][] chessboard) {
		if(row == n) {
			//把数组行转换为字符串,然后加入到队列中
			StringBuilder sb = new StringBuilder();
			List<String> method = new ArrayList<>();
			for(int i=0;i<chessboard.length;i++) {
				for(int j=0;j<chessboard.length;j++) {
					sb.append(chessboard[i][j]);
				}
				method.add(sb.toString());
				sb = new StringBuilder();
			}
			//得出第一种解决方案
			result.add(new ArrayList<>(method));
			return;
		}
		for(int col=0;col<n;col++) {
			if(isValid(row, col, chessboard, n)) {// 验证合法就可以放
				chessboard[row][col] = "Q";// 放置皇后
				backtracking(n, row+1, chessboard);
				chessboard[row][col] = ".";// 回溯，撤销皇后
			}
		}
	}
	public boolean isValid(int row, int col, String[][] chessboard, int n) {
		// 检查列
		for(int i=0;i<row;i++) {
			if(chessboard[i][col] == "Q") {// 这是一个剪枝
				return false;
			}
		}
		// 检查 45度角是否有皇后
		for(int i=row-1,j=col-1;i>=0 && j>=0;i--,j--) {
			if(chessboard[i][j] == "Q") {
				return false;
			}
		}
		// 检查 135度角是否有皇后
		for(int i=row-1,j=col+1;i>=0 && j<n;i--,j++) {
			if(chessboard[i][j] == "Q") {
				return false;
			}
		}
		return true;
	}
	
	//方法一：基于集合的回溯
	public List<List<String>> solveNQueens1(int n) {
        List<List<String>> solutions = new ArrayList<List<String>>();
        //记录女王在每一行的位置
        int[] queens = new int[n];
        Arrays.fill(queens, -1);
        // 检查列
        Set<Integer> columns = new HashSet<Integer>();
        // 检查 45度角是否有皇后
        Set<Integer> diagonals1 = new HashSet<Integer>();
        // 检查 135度角是否有皇后
        Set<Integer> diagonals2 = new HashSet<Integer>();
        backtrack(solutions, queens, n, 0, columns, diagonals1, diagonals2);
        return solutions;
    }
    public void backtrack(List<List<String>> solutions, int[] queens, int n, int row, Set<Integer> columns, Set<Integer> diagonals1, Set<Integer> diagonals2) {
        if (row == n) {
            List<String> board = generateBoard1(queens, n);
            solutions.add(board);
        } else {
        	//i为第几列
            for (int i = 0; i < n; i++) {
                if (columns.contains(i)) {
                    continue;
                }
                //方向一的斜线为从左上到右下方向，同一条斜线上的每个位置满足行下标与列下标之差相等
                int diagonal1 = row - i;
                if (diagonals1.contains(diagonal1)) {
                    continue;
                }
                //方向二的斜线为从右上到左下方向，同一条斜线上的每个位置满足行下标与列下标之和相等
                int diagonal2 = row + i;
                if (diagonals2.contains(diagonal2)) {
                    continue;
                }
                //保存皇后在第row行的位置
                queens[row] = i;
                columns.add(i);
                diagonals1.add(diagonal1);
                diagonals2.add(diagonal2);
                backtrack(solutions, queens, n, row + 1, columns, diagonals1, diagonals2);
                //回溯
                queens[row] = -1;
                columns.remove(i);
                diagonals1.remove(diagonal1);
                diagonals2.remove(diagonal2);
            }
        }
    }
    public List<String> generateBoard1(int[] queens, int n) {
        List<String> board = new ArrayList<String>();
        for (int i = 0; i < n; i++) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[queens[i]] = 'Q';
            //把char转换成String,记录一行数据
            board.add(new String(row));
        }
        return board;
    }
    //方法二：基于位运算的回溯
    public List<List<String>> solveNQueens2(int n) {
        int[] queens = new int[n];
        Arrays.fill(queens, -1);
        List<List<String>> solutions = new ArrayList<List<String>>();
        solve(solutions, queens, n, 0, 0, 0, 0);
        return solutions;
    }
    public void solve(List<List<String>> solutions, int[] queens, int n, int row, int columns, int diagonals1, int diagonals2) {
        if (row == n) {
            List<String> board = generateBoard2(queens, n);
            solutions.add(board);
        } else {
            int availablePositions = ((1 << n) - 1) & (~(columns | diagonals1 | diagonals2));
            while (availablePositions != 0) {
                int position = availablePositions & (-availablePositions);
                availablePositions = availablePositions & (availablePositions - 1);
                int column = Integer.bitCount(position - 1);
                queens[row] = column;
                solve(solutions, queens, n, row + 1, columns | position, (diagonals1 | position) << 1, (diagonals2 | position) >> 1);
                queens[row] = -1;
            }
        }
    }
    public List<String> generateBoard2(int[] queens, int n) {
        List<String> board = new ArrayList<String>();
        for (int i = 0; i < n; i++) {
            char[] row = new char[n];
            Arrays.fill(row, '.');
            row[queens[i]] = 'Q';
            board.add(new String(row));
        }
        return board;
    }
}
